The present invention relates to machine vision systems, and more particularly to a method and apparatus implementing thresholding in an automated vision inspection context.
Machine vision systems are known and widely in use for numerous inspection applications, including inspection of solder paste on printed circuit boards, location of defects on printed labels, and inspection of adhesives on a die, or the like. In many such automated inspection applications a basic issue addressed in the inspection process is a determination of the presence/absence, or measurement of a feature of interest (called the xe2x80x9cforegroundxe2x80x9d), e.g. solder or adhesive, within the context of a complex background. Complex backgrounds, e.g. the surface of a printed circuit board or a label or die, may include various geometric configurations, great variability in darkness and brightness, and/or light reflection and/or shadowing. Intricate backgrounds with a variety of gray levels, for example solder pads and board surface, and/or different polarities with respect to paste gray level values, make it difficult for the inspection system to discern the features of interest from the complexities of the background.
Segmentation is an important concept applied in machine vision for various inspection/location applications, such as those requiring the location/inspection of features of interest in complex backgrounds. Segmentation generally means discriminating (or segmenting) an image involved in a machine vision process into features of interest (i.e. foreground) and background, on a pixel by pixel basis.
Various techniques are known, and others have been proposed, for implementing segmentation in machine vision applications. Some segmentation implementations, such as those described in Gonzalez and Wintz, Digital Image Processing, Second Edition Section 7.3, pages 354-367, Addison-Wesley, 1987 involve computing histograms and then deriving suitable thresholds to segment the image. That is, the image is processed on a pixel by pixel basis to determine gray level values for the pixels, and the image pixels are correlated in accordance with frequency of occurrence of particular gray level values. A suitable fixed threshold in the form of a simple scalar value is ascribed to the image, above or below which a pixel will be designated either as a background pixel or as a pixel associated with a feature of interest.
However, segmentation via known thresholding techniques has limited applicability. In many applications the scenes are very complex and are thus not conducive to selection of a particular scalar value for discriminating between background and features of interest. For instance, within an image of an object under inspection there may be pixels relating to features of interest that have virtually the same gray level value as pixels relating to some background aspect. Further there may be a lot of variation of gray level values for pixels related to the same aspect of objects under inspection, from one image to another, so that use of a fixed scalar threshold value results in a particular pixel or set of pixels being designated as background in one image of an object under inspection and as a feature of interest in another image.
Image subtraction can be used to somewhat overcome the problems associated with segmentation of complex scenes. As known in the art, image subtraction is typically implemented in two different ways: in static methods, and in dynamic methods.
In static methods, a run-time image of the object under inspection or part is subtracted from a xe2x80x9cgolden image,xe2x80x9d i.e. an image of a known good representation of the part (referred to as a xe2x80x9cgolden samplexe2x80x9d). An example of a static method implementing image subtraction is a label inspection process that uses a xe2x80x9cGolden Template Comparisonxe2x80x9d vision tool as known in the art. Such a process typically involves a golden image of the label under inspection, which is subtracted from a respective image of each label inspected during run time. A respective difference image is used to identify differences between the object/label under inspection and the golden sample. The differences may be quantified as defects.
In dynamic image subtraction methods, two images of the same part taken at two different points in time are subtracted. An example of a dynamic method implementing image subtraction is a solder paste inspection process that uses an image of a printed circuit board (xe2x80x9cPCBxe2x80x9d) captured before solder is applied (a xe2x80x9cpre-imagexe2x80x9d), and an image of the same PCB after solder is applied (a xe2x80x9cpost-imagexe2x80x9d), for inspection that determines whether the solder was properly applied to the PCB. The pre-image is subtracted from the post-image so that a respective difference image is generated for each PCB inspected during run time. The difference image is used to identify differences between the pre-image and the post-image, which correspond to areas where solder paste has been applied.
After the image subtraction step, a thresholding step is necessary to binarize the difference image, assigning one value (i.e. xe2x80x9c0xe2x80x9d) to gray values in the difference image that are less than the threshold value (background), and another value (i.e. xe2x80x9c1xe2x80x9d) to gray values in the difference image that are equal to or greater than the threshold value (features of interest or foreground). This is followed by connectivity analysis to complete the segmentation process by relating or connecting adjacent pixels of the same binary value and identifying them as objects of interest or background.
Similar processing is involved in dynamic methods known in the art used for adhesive inspection on a printed circuit board or on a die, and envelope check box content identification which also use multiple images that are a function of multiple light sources.
Disadvantageously, the thresholding step used in known dynamic or static segmentation methods that involve image subtraction typically is achieved by using a simple scalar value as a threshold. In most practical cases this is inadequate and leads to difficulties in discriminating features of interest from background, especially if there is a complex background. Variations in gray level values of similar constructs within a single image and variations in gray level values of the same object from image to image make it difficult to select a single scalar threshold value. Process variations, such as variations in lighting and variations in appearance between objects under inspection, exacerbate the difficulty in locating/inspecting features of interest on complex background(s) using a scalar value threshold.
Similarly, polarities of gray level values of background that are greater or less than the gray level values of features of interest create difficulties in assigning a single threshold value for a given image. In some inspection implementations the background could have areas that are darker and some areas that are brighter than the feature of interest. If contiguous regions are of such opposite polarity, the xe2x80x9cedgexe2x80x9d or interface between the regions will transition through the gray level(s) of the feature of interest. In particular, in pre-post solder paste inspection implementations, at interface areas or edges where board meets solder pads and the gray value is substantially equal to the gray value of the solder paste, the subtraction operation results in interfaces going undetected, i.e. the areas of edges between the board and pad are effectively ignored.
The present invention provides a method and apparatus implementing dynamic thresholding techniques in processes that use image subtraction, such as in an automated vision inspection context.
According to the invention, in a foreground/background detection implementation a first image and a second image are first filtered with a median filter to produce a first filtered image and a second filtered image having reduced noise. The first and second filtered images are then subtracted resulting in a subtracted image. The subtracted image is separated into two components, using respective image maps. A positive image map is used to generate a positive difference image consisting of positive differences which are processed in a positive xe2x80x9cchannelxe2x80x9d, and a negative image map is used to generate a negative difference image consisting of absolute values of the negative differences which are processed in a negative xe2x80x9cchannelxe2x80x9d.
In the positive channel and the negative channel, respectively, a Gaussian filtered first image is subjected to a positive threshold map and a negative threshold map to generate respective positive and negative dynamic threshold images. The positive threshold map and the negative threshold map are pixel maps that: 1) mask out areas that are not relevant to the respective positive and negative channels, and 2) implement adaptive gain in the form of pixel thresholds that are proportional to a difference in gray level value or amount of contrast between the gray level value of the feature of interest in the foreground and the local background area, e.g. the difference or contrast between solder paste gray level value and board (or pad) value.
Thresholding is implemented in the positive channel by subtracting the positive difference image from the positive dynamic threshold image, providing a subtracted positive image. Likewise, thresholding is implemented in the negative channel by subtracting the negative difference image from the negative dynamic threshold image, providing a subtracted negative image. The subtracted positive and subtracted negative images are each passed through a common conversion map to eliminate negative values and provide a positive results image and a negative results image wherein positive values are set to 255 (pixels that were greater than the threshold) and the rest are set to 0. Next, the two channels. i.e. the positive results image and the negative results image are combined to provide a merged image. The merged image is then binarized to provide binarized foreground/background detection output wherein all positive values, i.e. pixels representing features of interest in the foreground (e.g. solder on a pad), are set to xe2x80x9c1xe2x80x9d and zero values, i.e. background pixels, are set to xe2x80x9c0xe2x80x9d.
In some inspection implementations the background may have some areas that are darker and some areas that are brighter than the feature of interest. If contiguous regions are of such opposite polarity, the xe2x80x9cedgexe2x80x9d or interface between the regions will transition through the gray level(s) of the feature of interest. In particular, in pre-post solder paste inspection implementations, at interface areas or edges where background meets solder pads and the gray value is substantially equal to the gray value of the solder paste, the subtraction and dynamic thresholding operations result in interfaces going undetected, i.e. the areas of edges between the board and pad are ignored. According to the invention, interface detection is handled by an edge interface algorithm.
In further accord with the pre-post solder paste inspection implementation according to the invention, interface detection involves initially processing the pre-image and the post-image with a median filter to reduce noise and provide a filtered pre-image and a filtered post image. The filtered pre and post images are then passed through an edge detector, followed by peak detection to find the edge peaks and provide an edge peak pre-image and an edge peak post image. Next, a binarization map is used to convert the edge peak pre and post images to respective 8-bit binary images (i.e. binary edge pre-image, binary edge post image), where the presence of an edge peak is denoted by a value of 255 and the lack of a peak is denoted by a value of 0. The edge peak post image is then dilated to compensate for sub-pixel mis-registration (forming a dilated post image). The dilated post image is then subtracted from the binary edge pre-image to form an edge subtraction image. If a pixel was associated with an edge in the pre-image and was absent from the dilated post image then the result of the subtraction for that pixel is positive (255), and it is assumed that it must be occluded by paste in the post-image, and hence that edge pixel must constitute a paste pixel.
The resultant edge subtraction image is then mapped to get rid of any negative values and provide an edge difference image having all positive and zero values. The edge difference image is dilated to account for slow transitioning interfaces or edges, and binarized to set the positive values to xe2x80x9c1xe2x80x9d and the zero values to xe2x80x9c0xe2x80x9d.
Ultimately, the two binary images (i.e. the binarized foreground/background detection output and the binarized edge detection output) are merged using a binary-OR operation, to form a merged binary image. The merged binary image is then subjected to a morphological filter to effect cleanup, and a connectivity operation is effected in accordance with a specified minimum feature area, to obtain an indication of position and size of contiguous paste regions.
Features of the invention include a flexible dynamic thresholding implementation that is applicable in a variety of vision system subtraction contexts. For example, the type of first image and second image subtracted in a foreground/background detection implementation can be, respectively, a pre-image and post-image, a golden sample model image and a runtime image, or an image under first lighting conditions and another image under second lighting conditions.
Advantageously, the use of an effective dynamic threshold image such that each pixel in the subtracted image has its own threshold value results in a local threshold, rather than a fixed single scalar threshold value, which allows for adapting the threshold to the background locally within an image. The threshold image, which is derived from the background image (first or pre-image) is dynamic as it is generated for every new part that is processed and therefore the method and apparatus according to the invention has a higher level of tolerance for differences between images of a single object type. Greater flexibility in thresholding, and consequently more accurate segmentation, is provided by use of both positive and negative difference images which are subtracted/compared against separate threshold images.
The implementation of adaptive gain results in proportionate thresholding, in that the greater the difference between the background gray level value(s) and the gray level value(s) of the feature(s) of interest, the greater the contrast (subtraction value), and therefore the value of the threshold is increased proportionately. This feature permits the method and apparatus according to the invention to adapt to varying backgrounds by being more unbiased in passing signal relative to noise. It also allows for having the highest possible threshold for each background to permit more accurate discrimination.
Although the thresholding according to the invention is dynamic, a simple linear function is used to derive the dynamic threshold(s) from the background. The slopes of the linear functions used to derive the threshold images for the two different polarities are independent and advantageously facilitate flexibility in implementing adaptive gain as a function of the application. Masking implemented in the independent channel threshold maps ensures that difference values in areas of background with the wrong polarity are ignored and will not pose problems discriminating foreground from background. For example, areas on a solder pad which get brighter due to any spurious reflections can be ignored, since the solder paste is darker than the pad.
Furthermore, a more robust segmentation is facilitated, as compared to prior art segmentation/thresholding implementations which typically assume that there are no regions of the background with the same gray level as the feature(s) of interest. This assumption is not always reasonable in that it is violated at the edges of the background. In the method and apparatus according to the invention, the edge interface between pads and boards, which transitions through and may have at some pixels the same gray levels as the solder paste, can be discriminated as the edge interface between the different areas of the background are handled separately.